﻿#include <algorithm>
#include <gtest/gtest.h>
#include <iostream>
#include <random>
#include <vector>

#include <xy/utils/sort.h>

#define TIMES 100
#define BUF_SIZE 100

using namespace xy::utils;

TEST(TestSort, bubble_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        bubble_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, insert_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        insert_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, binary_insert_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        binary_insert_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, shell_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        shell_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, merge_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        merge_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, quick_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        quick_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, heap)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        make_heap(arr, BUF_SIZE);
        std::make_heap(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }

        heap_sort(arr, BUF_SIZE);
        std::sort_heap(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}